#include <stdlib.h>
#include <typeinfo>
#include "dom.h"

/***********************
 The Lengauer-Tarjan Algorithm
 ***********************/

namespace cilast {
    
    int id;	//global id
    
    int n;	//local id for cfg
    stmt** vertex;
    int* parent;
    int* ancestor;
    int* semi;
    
    std::vector<int>** bucket;
    
    stmt* get_entry(fundec* cfg) {
        return cfg->sbody->bstmts.back();
    }
    
    stmt* get_ret(fundec* cfg) {
        return cfg->sbody->bstmts.front();
    }
    
    std::vector<stmt*>* get_ins(stmt* node) {		
        return &(node->succs);
    }
    
    std::vector<stmt*>* get_outs(stmt* node) {
        return &(node->preds);
    }
    /*
     inline CFNode* get_idom(CFNode* node) {
     if(fwd)
     return node->idom;
     else
     return node->ipostdom;
     }
     */
#define get_idom(node) node->ipostdom
    
    /*
     inline void set_idom(CFNode* node, CFNode* idom) {
     if(fwd)
     node->idom = idom;
     else
     node->ipostdom = idom;
     }
     */
#define set_idom(node, idom) node->ipostdom = idom
    
    
    void DFS(stmt* curr) {
        int i;
        stmt* next;
        curr->did = ++n;
        semi[curr->did] = curr->did;
        
        std::vector<stmt*>* outs = &(curr->preds);
        for(i=0;i<outs->size();i++) {
            next = outs->at(i);
            
            if(next->did==0) { //un-processed
                DFS(next);
                parent[next->did] = curr->did;
            }
        }
        vertex[curr->did] = curr;
    }
    
    void init_dom(fundec* cfg) {
        int num = cfg->smaxstmtid + 1; //g_hash_table_size(cfg->nodes)+1; // index 0 is for null
        
        n = 0;	//0 stands for null. n starts from 1.
        
        //reset id
        /*gpointer key, value;
         GHashTableIter iter;
         g_hash_table_iter_init (&iter, cfg->nodes);
         while (g_hash_table_iter_next (&iter, &key, &value))  {
         ((CFNode*)value)->id = 0;
         }*/
        vertex = new stmt*[num] ();//(stmt**)calloc(num, sizeof(stmt*));
        parent = new int[num] ();//(int*)calloc(num, sizeof(int));
        ancestor = new int[num] ();//(int*)calloc(num, sizeof(int));
        semi = new int[num] ();//(int*)calloc(num, sizeof(int));
        
        bucket = new std::vector<int>*[num];
        for(int i=0; i<num; i++)
            bucket[i] = new std::vector<int>();
        
        for(int i=0; i<num-1; i++) {
            cfg->sallstmts[i]->did = 0;
            cfg->sallstmts[i]->ipostdom = NULL;
        }
        DFS(get_entry(cfg));
    }
    
    void final_dom() {    
        delete [] vertex;
        delete [] parent;
        delete [] ancestor;
        delete [] semi;
        
        
        for(int i=0; i<n; i++)
            delete bucket[i];
        delete [] bucket;
        
    }
    
    void LINK(int v, int w) {
        ancestor[w] = v;
    }
    
    int EVAL(int v) {
        int a;
        
        for(a=ancestor[v]; ancestor[a]!=0; a = ancestor[a]) {
            if(semi[v]>semi[a])
                v = a;
        }
        return v;
    }
    
    void compute_idom() {
        int i, j, v, u, w;
        stmt* curr;
        
        for(i=n; i>=2; i--) {
            curr = vertex[i];
            w = curr->did;	
            
            //step2
            std::vector<stmt*>* ins = &(curr->succs);
            for(j=0; j<ins->size(); j++) {
                v = ins->at(j)->did;
                u = EVAL(v);
                if(semi[u]<semi[w])
                    semi[w] = semi[u];
            }
            bucket[semi[w]]->push_back(w);
            
            LINK(parent[w],w);
            
            //step3
            for(j=0; j<bucket[parent[w]]->size(); j++) {
                v = bucket[parent[w]]->at(j);
                u = EVAL(v);
                if(semi[u]<semi[v])
                    set_idom(vertex[v], vertex[u]);
                else
                    set_idom(vertex[v], vertex[parent[w]]);
            }
            bucket[parent[w]]->clear();
            
        }
        
        //step4
        for(i=2; i<=n; i++) {
            curr = vertex[i];
            if(get_idom(curr) != vertex[semi[curr->did]])			
                set_idom(curr, get_idom(get_idom(curr)));
            //curr->id = curr->id + id;
        }
        set_idom(vertex[1], vertex[1]);
        //vertex[1]->id = vertex[1]->id + id;
        
        
    }
    
    void computeIPDom(fundec* cfg) {
        init_dom(cfg);
        compute_idom();
        //id = id + n;
        final_dom();
    }
    
    
    
    class ipdVisitor : public astVisitor {
        
        int visit(GFun* gfun) {
            computeIPDom(gfun->mfundec);
            
        }
        
    };
    
    void computeFileIPDom(file* f) {
        std::vector<global*>* globals = &(f->globals);
        
        std::vector<global*>::iterator it;
        for(it=globals->begin(); it<globals->end(); it++) {
            (*it)->accept(new ipdVisitor());
        }
    }
    
    
    
}